/** 

问题：
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
请你设计一个算法来计算你所能获取的最大利润，你最多可以完成两笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
**/

/**
如果我是在历史最低点买的股票就好了！太好了，在题目中，我们只要用一个变量记录一个历史最低价格 minprice
 */
public class Solution {
   public  int maxProfit(int[] prices) {
    if (prices == null || prices.length == 0)
        return 0;
    int maxPro = 0;//记录最大利润
    int min = prices[0];//记录数组中访问过的最小值
    for (int i = 1; i < prices.length; i++) {
        min = Math.min(min, prices[i]);
    }
    for (int i = 1; i < prices.length; i++) {
        maxPro = Math.max(prices[i] - min, maxPro);
    }
        return maxPro;
    }
}



/**

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 */

 /**
 在所有的上涨时候买入股票
  */

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            int tmp = prices[i] - prices[i - 1];
            if (tmp > 0) profit += tmp;
        }
        return profit;
    }
}




/**
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。


/**

本题中存在三种「状态」：天数、是否持有股票的状态、交易次数
而对于每种状态，我们又有不同的选择：
1. 天数由prices确定
2. 是否持有股票的状态我们可以用0/1表示，0代表不持有股票，1代表持有股票
3. 交易次数由k确定

因为对于第0天来说，它所能够获取的最大利润只有两种，与交易次数毫无关系，所以我们有以下初始值：
1.不持有股票时：dp[0][0][k]=0
2.持有股票时：dp[0][1][k]=-prices[0]

第i天不持有股票时：
1.如果第i-1天也不持有股票，那就代表状态不变，第i天的状态=第i-1天的状态
2.如果第i-1天持有股票，说明我们在第i天把股票卖了，既然卖股票赚钱了，利润就要多prices[i]
dp[i][0][k] = max(dp[i-1][0][k] , dp[i-1][1][k]+prices[i])

第i天持有股票时：
1.如果第i-1天也持有股票，那就代表状态不变，即dp[i][1][k] = dp[i-1][1][k]
2.如果第i-1天不持有股票，说明我们在第i天买入股票，既然买股票要花钱，利润就要少price[i]
买入股票的同时，当天的交易次数要在前一天的基础上+1

dp[i][1][k] = max(dp[i-1][1][k] , dp[i-1][0][k-1]-prices[i])

 **/

class Solution {
    public int maxProfit(int K, int[] prices) {//这里悄咪咪把小k换成了大K，便于后续索引赋值
        int n=prices.length;
        if(n<=1)    return 0;
        //因为一次交易至少涉及两天，所以如果k大于总天数的一半，就直接取天数一半即可，多余的交易次数是无意义的
        K=Math.min(K,n/2);

        /*dp定义：dp[i][j][k]代表 第i天交易了k次时的最大利润，其中j代表当天是否持有股票，0不持有，1持有*/
        int[][][] dp=new int[n][2][K+1];
        for(int k=0;k<=K;k++){
            dp[0][0][k]=0;
            dp[0][1][k]=-prices[0];
        }

        /*状态方程：
        dp[i][0][k]，当天不持有股票时，看前一天的股票持有情况
        dp[i][1][k]，当天持有股票时，看前一天的股票持有情况*/
        for(int i=1;i<n;i++){
            for(int k=1;k<=K;k++){
                dp[i][0][k]=Math.max(dp[i-1][0][k],dp[i-1][1][k]+prices[i]);
                dp[i][1][k]=Math.max(dp[i-1][1][k],dp[i-1][0][k-1]-prices[i]);
            }
        }
        return dp[n-1][0][K];
    }
}

309. 最佳买卖股票时机含冷冻期：含有交易冷冻期
冷冻期就是：卖出股票后，你无法在第二天买入股票，那又有何难
直接设置三个持有状态：
dp[i][0]：持有股票
dp[i][1]：不持有股票，处于冷冻期
dp[i][2]：不持有股票，不处于冷冻期

dp[i][0]=max(dp[i-1][0] , dp[i-1][2]-prices[i]) //当天持有股票，前一天不可能是冷冻期，也就没有dp[i-1][1]
dp[i][1]=dp[i-1][0]+prices[i] //当天是冷冻期，只可能是前一天持有股票，然后今天卖出股票了
dp[i][2]=max(dp[i-1][1],dp[i-1][2]) //当天是非冷冻期，前一天不可能持有股票

714. 买卖股票的最佳时机含手续费：每次交易含手续费
dp[i][0]=max(dp[i-1][0] , dp[i-1][1]+prices[i]-fee) //卖出股票时完成一次交易，支付手续费
dp[i][1]=max(dp[i-1][1] , dp[i-1][0]-prices[i])

作者：Destinytomycode
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/javayi-ge-si-lu-da-bao-suo-you-gu-piao-t-pd1p/